package com.lsa.letcode.the62.uniquePath;

public class Main {
	public static void main(String[] args) {
		int n = 5;
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				System.out.print(String.format("(%s,%s)", i, j));
			}
			System.out.println();
		}
		
		System.out.println(C_n_k(7, 3));
	}
	
	private static int C_n_k(int n, int k) {
		int[][] C_n_k = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			C_n_k[i][0] = 1;
		}
		for (int i = 1; i <= n; i++) {
			C_n_k[i][i] = 1;
		}
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				C_n_k[i][j] = C_n_k[i - 1][j - 1]  + C_n_k[i - 1][j];
				if (i == n && j == k) {
					return C_n_k[i][j];
				}
			}
		}
		return  C_n_k[n][k];
	}
}
